#include <stdio.h>
#include <malloc.h>
#include <string>

#define MAX_SIZE 100

typedef struct
{
    char data[MAX_SIZE];
    int length; 
}SqString; 

static void destroy_str(SqString &s)
{

}


static void str_assign(SqString &s, char cstr[])
{
    int i;

    for(i = 0; cstr[i] != '\0'; i++)
        s.data[i] = cstr[i];
    s.length = i;
}


static void disp_str(SqString s)
{
    int i;

    if(s.length > 0)
    {
        for(i = 0; i < s.length; i++)
            printf("%c", s.data[i]);
        printf("\n");
    }
}

static SqString *max_sub_str(SqString s)
{
    SqString *subs;
    int index = 0; 
    int length = 0; 
    int i = 0, j, k;
    int length1;

    while(i < s.length)
    {
        j = i + 1;
        while(j < s.length)
        {
            if(s.data[i] == s.data[j]) 
            {
                length1 = 1;
                for(k = 1; s.data[i + k] == s.data[j + k]; k++)
                    length1++;
                if(length1 > length) 
                {
                    index = i;
                    length = length1;
                }
                j += length1;
            }
            else
                j++;
        }
        i++;
    }

    subs = (SqString *)malloc(sizeof(SqString));
    subs->length = length;
    for(i = 0; i < length; i++) 
        subs->data[i] = s.data[index + i];
    return subs;
}

int main(int argc, char *argv[])
{
    char *gets(char *str);
    char str[MAX_SIZE];
    SqString s, *subs;
    printf("输入串:");
    gets(str);
    str_assign(s, str); 
    subs = max_sub_str(s);
    printf("求最长重复子串:\n");
    printf("    原串:");
    disp_str(s);
    printf("  最长重复子串:"); 
    disp_str(*subs);
    destroy_str(s);
    free(subs);
    return 0;
}

